#include <stdio.h>
#include <stdlib.h>

// 块的定义，包含每个块的起始索引和块内的最大值
typedef struct {
    int max_value;  // 块的最大值
    int start_index; // 块的起始索引
} Block;

// 顺序查找函数，在块内查找目标元素
int sequentialSearch(int arr[], int start, int end, int key) {
    for (int i = start; i <= end; i++) {
        if (arr[i] == key) {
            return i;  // 找到，返回元素索引
        }
    }
    return -1;  // 未找到，返回-1
}

// 分块查找函数
int blockSearch(int arr[], Block blocks[], int num_blocks, int block_size, int key) {
    // 在索引表中查找目标元素可能的块
    int i;
    for (i = 0; i < num_blocks; i++) {
        if (key <= blocks[i].max_value) {
            break;  // 找到对应的块
        }
    }
    
    if (i == num_blocks) {
        return -1; // 没有找到对应的块
    }
    
    // 在对应块内进行顺序查找
    int start = blocks[i].start_index;
    int end = (i + 1) * block_size - 1;
    // 检查末尾是否超出数组范围
    if (end >= block_size * num_blocks) {
        end = block_size * num_blocks - 1;
    }

    return sequentialSearch(arr, start, end, key); // 在块内查找目标元素
}

int main() {
    // 假设我们有一个数组（块与块之间有序，但块内可能无序）
    int arr[] = {5, 3, 8, 10, 14, 17, 20, 24, 28, 32, 37};
    int n = sizeof(arr) / sizeof(arr[0]);

    // 定义分块大小
    int block_size = 4;
    int num_blocks = (n + block_size - 1) / block_size;  // 计算块数

    // 创建块的索引表
    Block blocks[num_blocks];
    
    // 填充索引表
    for (int i = 0; i < num_blocks; i++) {
        blocks[i].start_index = i * block_size;
        // 每个块的最大值是该块最后一个元素
        if ((i + 1) * block_size - 1 < n) {
            blocks[i].max_value = arr[(i + 1) * block_size - 1];
        } else {
            blocks[i].max_value = arr[n - 1];  // 最后一块可能不满
        }
    }

    // 进行分块查找
    int key = 24;  // 我们想要查找的元素
    int result = blockSearch(arr, blocks, num_blocks, block_size, key);

    // 输出结果
    if (result != -1) {
        printf("Element %d found at index %d\n", key, result);
    } else {
        printf("Element %d not found\n", key);
    }

    return 0;
}
